/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        int n = inorder.size();
        if (n == 1) return new TreeNode(inorder[0]);

        return dfs(inorder, 0, n - 1, postorder, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& in, int begin1, int end1, vector<int>& post, int begin2, int end2)
    {
        TreeNode* root = new TreeNode(post[end2]);

        if (begin2 == end2) return root;
        int mid = begin1;
        while (in[mid] != post[end2]) mid++;
        int lenth = mid - begin1;

        if (mid > begin1)
            root->left = dfs(in, begin1, mid - 1, post, begin2, begin2 + lenth - 1);
        if (mid < end1)
            root->right = dfs(in, mid + 1, end1, post, begin2 + lenth, end2 - 1);
        return root;
    }
};